The original lodge 71 was chartered to Monmouth Council on October 5, 1933 with the name Ohowa. The lodge totem was an owl. Activities of Ohowa lodge probably centered around the council's camp, Camp Burton-at-Allaire.

The lodge became inactive by about 1940, around the same time summer camp at Camp Burton-at-Allaire was discontinued.

In 1937 the council was renamed Monmouth-Ocean Council in recognition of the growth of the Scouting program in Ocean county.

In 1940, Monmouth-Ocean Council split into two councils: Monmouth Council and Ocean County Council. At that time, the new Ocean County Council scout executive requested that lodge number 71 be assigned to Ocean County Council. However, there is no record of any Order of the Arrow activity in either council at that time. Following World War II, the lodge number was again available, and the Monmouth Council scout executive received approval to reactivate lodge 71. But again it appears that there was not enough interest at the grassroots to revive the old lodge.

A small group of youth and adults gathered in December 1950 at Camp Housman on the old Allaire property just one mile from where the original Ohowa lodge 71 had been founded. They formed a new lodge called Na-Tasi-Hi, which meant "in the pines"-- a reference to Camp Housman's location on the northern fringe of the Pine Barrens. The lodge's totem would be "three pine trees" to represent the three parts of the Scout Oath and the three principles of the OA.

The new lodge was approved by the council's executive board and received its National charter (re-using the old number 71) in early 1951. During 1951, the spelling of the lodge's name was corrected by changing Tasi to Tsi, which is the proper spelling of that syllable in the Cherokee language, resulting in the name Na-Tsi-Hi.

The lodge sent a contingent to the first Area 2-C Conference, at Pine Hill Scout Reservation in 1951.