The position of Marshall was created by the 1869 City Charter, a position with traditional policing duties. The first time the word "police" was used in legislative language may be Ordinance 66 ("In relation to Police powers"), passed between November 13th, 1874 and January 22nd, 1875. The 1875 amendments to the City Charter gave the city power "to establish and maintain a day and night police" and provided that the city could elect or appoint as many police officers as deemed necessary. Concurrently, however, the language about a City Marshall was maintained. Ordinance 97 ("An ordinance concerning offenses and disorderly conduct"), passed March 3rd, 1876, still referred to a City Marshall and a Deputy Marshall. The City Charter Amendments of 1883 included a house cleaning section, stating that any reference in the Charter to the Marshall should be construed to mean Chief of Police, who had the authority to hire police officers. This amendment was the first time the term Chief of Police appeared in the Charter:

"The Chief of Police shall be the peace officer of the city, and must execute all process issued by the police justice […]. He shall execute vigilant control over the peace and quiet of the city; shall be the keeper of the city prison, […]. Wherever the word marshal occurs in said act the same shall be taken to mean Chief of Police […]." Until 1890, the Chief of Police was elected by voters of the City for a one-year term. The Freeholders City Charter of 1890 created a five-member Board of Police Commissioners to oversee and administer the operations of the Police Department. The Commission, chaired by the Mayor, had the authority to appoint the Chief of Police and appoint officers:

"The Police Department shall be under the management of a Police Commission, to consist of the mayor, who shall be chairman of the commission, and four (4) police commissioners [… who] shall hold the office for four (4) years."

Following allegations of corruption, the Board of Police Commissioners was abolished by the new Freeholders City Charter of 1896. The Chief of Police, appointed by the mayor, served as administrator of the Department:

"There shall be a police department, which shall consist of a Chief of Police and as many subordinate officers, detective officers, and regular and special policemen as the city council shall from time to time by ordinance prescribe. […] The mayor shall appoint the Chief of Police […] and may remove him in his discretion […]. The mayor shall prescribe rules and regulations […] for the government and control of the police department."

A City Charter Amendment in 1936 provided for the Chief of Police to be appointed for a five year term of office. A new Freeholders City Charter was adopted March 12, 1946. Under its provisions, the term of the Chief of Police was not specified.

In 1962, the Department assumed authority for policing the harborfront, formerly a function of the Harbor Department.