All of NY 104A was originally part of Route 30, an unsigned legislative route, during the early 20th century. In 1924, modern NY 104A became part of NY 3, then a cross-state highway that continued west to Niagara County. U.S. Route 104 (US 104) replaced most of NY 3 between Rochester and Maple View in April 1935. From Red Creek to Oswego, however, US 104 used a more southeasterly alignment via Hannibal. The Red Creek–Oswego segment of NY 3 became NY 104A instead.