Fenollosa was the son of Manuel Francisco Ciriaco Fenollosa and Mary Silsbee (Fenollosa) and attended Hacker Grammar School in Salem, Massachusetts, and the Salem High School before graduating from Harvard College in the class of 1874. He then studied at Cambridge University in philosophy and divinity. After a year at the art school at the Boston Museum of Fine Arts, during which time he married Lizzie Goodhue Millett, he traveled to Japan in 1878 at the invitation of American zoologist and Orientalist Edward S. Morse to teach political economy and philosophy at the Imperial University at Tokyo. There he studied ancient temples, shrines and art treasures with his assistant, Okakura Kakuzō.
During his time in Japan, Fenollosa helped revive the Nihonga (Japanese) style of painting with Japanese artists Kanō Hōgai (1828–1888) and Hashimoto Gahō (1835–1908). After eight years at the University, he helped found the Tokyo Fine Arts Academy and the Imperial Museum, then acting as its director in 1888. In this period, he helped to draft the text of a law for the preservation of temples and shrines and their art treasures. Fenollosa converted to Buddhism and changed his name to Tei-Shin, also adopting the name Kanō Yeitan Masanobu, suggesting that he had been admitted into the ancient Japanese art academy of the Kanō. While resident in Japan, Fenollosa's accomplishments included the first inventory of Japan's national treasures, leading to the discovery of ancient Chinese scrolls brought to Japan by traveling Zen monks centuries earlier. For these accomplishments, the Emperor of Japan decorated him with the orders of the Rising Sun and the Sacred Mirror.
In 1886, he sold his art collection to Boston physician Charles Goddard Weld (1857–1911) on the condition that it go to the Boston Museum of Fine Arts, and in 1890 he returned to Boston to be its curator of the department of Oriental Art. There Fenollosa was asked to choose Japanese art for exhibition at the 1893 World Columbian Exposition in Chicago. He also organized Boston's first exhibition of Chinese painting in 1894. In 1896, he published Masters of Ukioye, a historical account of Japanese paintings and color prints exhibited at the New York Fine Arts Building. However, his public divorce and immediate remarriage in 1895 to the writer Mary McNeill Scott (1865–1954) outraged Boston society, leading to his dismissal from the Museum in 1896.
He journeyed back to Japan in 1897 to accept a position as Professor of English Literature at the Tokyo Higher Normal School at Tokyo. Lafcadio Hearn considered Fenollosa a friend; and Hearn almost believed that he visited the professor's home too often.
In 1900, he returned to the United States to write and lecture on Asia. His 1912 work in two volumes concentrates on art before 1800 but offers Hokusai's prints as a window of beauty after Japanese art had become too modern for Fenollosa's taste: "Hokusai is a great designer, as Kipling and Whitman are great poets. He has been called the Dickens of Japan."
After his death, Fenollosa's unpublished notes on Chinese poetry and Japanese Noh drama were confided by his widow to noted poet Ezra Pound who, with William Butler Yeats, used them to solidify the growing interest in Far Eastern literature among modernist writers. Pound subsequently finished Fenollosa's work with the aid of Arthur Waley, the noted British sinologist.