A half-doped LaSrCoMnO6 (LSCMO) double perovskite synthesized by sol-gel method exhibits the coexistence of two perovskite phases, cubic (Fm-3m) and monoclinic (P21/n) crystal structures with volume ratio of 0.88:0.12. We have investigated the magnetic, dielectric, and magneto-dielectric properties of LSCMO. The magnetization measurement reveals that there exist two magnetic phase transitions at 266 K and 197 K corresponding to order and disorder magnetic phases, respectively. The dielectric and magneto-dielectric relaxations observed at 100 kHz around magnetic transition clearly provide an evidence of the correlation between dielectric and magnetic ordering. The relaxation process across the potential barriers leads to two anomalies before and after the magnetic phase transition temperature. The highest magneto-dielectric response is obtained to be 8.2% in the vicinity of the observed magnetic transition temperature. Modulus spectrum analysis reveals the intrinsic contribution to the magneto-dielectric behavior.