This Colloquium explores the joint role that nuclear plus particle physics and gravitational waves can play in telling us about
the deep structure of matter and physics of the early Universe. Physics topics include the structure of neutron stars and the origin of heavy elements, phase transitions in the early Universe, black holes (also in connection with dark matter candidates), polarization of the Cosmic Microwave Background as a probe of inflation, dark energy and what the Higgs boson might be telling us as a clue to deeper physics. New synergies between nuclear/particle physics and gravitational waves can play an essential role in our quest to understand the structure of dense nuclear matter and to access unexplored new physics. FAIR, the high luminosity upgrade of the LHC and the LISA gravitational waves mission plus other key experiments will provide exciting data in the next decade.