We report the study of three structural isomers of phenylpropiolonitrile (3-phenyl-2-propynenitrile, C6H5-C3N) containing an alkyne function and a cyano group, namely ortho-, meta-, and para-cyanoethynylbenzene (HCC-C6H4-CN). The pure rotational spectra of these species have been recorded at room temperature in the millimeter-wave domain using a chirped-pulse spectrometer (75-110 GHz) and a source-frequency modulation spectrometer (140-220 GHz). Assignments of transitions in the vibrational ground state and several vibrationally excited states were supported by quantum chemical calculations using the so-called "Lego brick" approach [A. Melli, F. Tonolo, V. Barone and C. Puzzarini, J. Phys. Chem. A, 2021, 125, 9904-9916]. From these assignments, accurate spectroscopic (rotational and centrifugal distortion) constants have been derived: for all species and all observed vibrational states, predicted rotational constants show relative accuracy better than 0.1%, and often of the order of 0.01%, compared to the experimental values. The present work hence further validates the use of the "Lego brick" approach for predicting spectroscopic constants with high precision.