A novel ethynyl addition mechanism (EAM) has been established computationally as a practicable alternative to high-temperature hydrogen-abstraction-C2H2-addition (HACA) sequences to form polycyclic aromatic hydrocarbon (PAH)-like species under low-temperature conditions in the interstellar medium and in hydrocarbon-rich atmospheres of planets and their moons. Initiated by an addition of the ethynyl radical (C2H) to the ortho-carbon atom of the phenylacetylene (C6H5C2H) molecule, the reactive intermediate loses rapidly a hydrogen atom, forming 1,2-diethynylbenzene. The latter can react with a second ethynyl molecule via addition to a carbon atom of one of the ethynyl side chains. A consecutive ring closure of the intermediate leads to an ethynyl-substituted naphthalene core. Under single-collision conditions as present in the interstellar medium, this core loses a hydrogen atom to form ethynyl-substituted 1,2-didehydronaphthalene. However, under higher pressures as present, for example, in the atmosphere of Saturn's moon Titan, three-body reactions can lead to a stabilization of this naphthalene-core intermediate. We anticipate this mechanism to be of great importance to form PAH-like structures in the interstellar medium and also in hydrocarbon-rich, low-temperature atmospheres of planets and their moons such as Titan. If the final ethynyl addition to 1,2-diethynylbenzene is substituted by a barrierless addition of a cyano (CN) radical, this newly proposed mechanism can even lead to the formation of cyano-substituted naphthalene cores in the interstellar medium and in planetary atmospheres.