Conventional paramagnetism-a state with finite magnetic moment per ion sans long range magnetic ordering, but with lowering temperature the moment each ion picks up a particular direction, breaking spin rotational symmetry, and results into long-range magnetic ordering. However, in systems with competing multiple degrees of freedom this conventional notion may easily break and results into short range correlation much above the global magnetic transition temperature. La2CuIrO6 with complex interplay of spins (s = 1/2) on Cu site and pseudo-spin (j = 1/2) on Ir site owing to strong spin-orbit coupling provides fertile ground to observe such correlated phenomena. By a comprehensive temperature dependent Raman study, we have shown the presence of such a correlated paramagnetic state in La2CuIrO6 much above the long-range magnetic ordering temperature (T N ). Our observation of strong interactions of phonons, associated with Cu/Ir octahedra, with underlying magnetic degrees of freedom mirrored in the observed Fano asymmetry, which remarkably persists as high as ~3.5T N clearly signals the existence of correlated paramagnetism hence broken spin rotational symmetry. Our detailed analysis also reveals anomalous changes in the self-energy parameters of the phonon modes, i.e. mode frequencies and linewidth, below T N , providing a useful gauge for monitoring the strong coupling between phonons and magnetic degrees of freedom.