When the City of Miami was incorporated in 1896, groups of black masons living in the Colored Town/Overtown area had to travel to the Coconut Grove Lodge for regular meetings. Since the lodge meetings were normally held in the late evenings it was difficult for working class blacks from Colored Town/Overtown to attend. At that time, blacks were not allowed to travel in and through the white areas of Miami without a special pass or work permit.

In 1901, a group of members from the Colored Town/Overtown area petitioned the Grand Lodge of the State of Florida finally honored that petition, extended the members a charter, and the group became the New Providence Lodge #365. Reverend A. J. Taylor served as the first Worshipful Master of the newly chartered lodge. The first meetings were held in the Love and Charity Building at Northwest Third Avenue and Eleventh Street.

Believing that they could serve community residents better with their own building, they purchased a piece of property on Northwest Third Avenue and Ninth Street in 1947, and began working towards their goal. Like many of the original structures in the Colored Town/Overtown area, the Lodge was built in the evenings. Members would meet after work to help with the construction. That same year they completed construction and named the building New Providence Lodge Temple #365. The temple was dedicated in 1954 and the structure still stands today at 941 NW 3^rd Avenue. It is the second oldest temple in Dade County, and the first to be built by its own members. 

Since its first meeting, the lodge has inaugurated fifteen Worshipful Masters: Joe Dark, Benjamin Gilbert, Jordan Dawkins, Ed Wilson, Thomas Pedican, James McPhee, John Gilbert, Willard Hart, David Mumford, Aubrey Brunson, Sherman Bullard, Richard El’ Amin, Ronald Cason, and the most recently, Tracy Yalledy.

The New Providence Lodge #365 has served the community for decades. Over the years many prominent and illustrious members have passed through the doors of the lodge: William O. Perry, Sr., Clyde Killens, Willard Hart, Garth Reeves, Dr. I. P. Davis, Rev. J. W. Drake, Rev. Evans, Dr. H. H. Greene, Dr. Murrel, Shaddie Ward, and many, many more.