Lead cobalt niobate (PbCo1/3Nb2/3O3: PCN) is a multifunctional relaxor electroceramic which are very popular due to their extraordinary properties and applications. To the best of our knowledge magnetoedielectric study of PCN ceramic has not been reported. We performed magnetodielectric measurement on PCN ceramic synthesized by two step columbite precursor method. Microstructure images revealed closely packed grains with grain size ~8-10 μm. Room temperature XRD pattern suggests single phase pseudo cubic crystal structure having Pm3m symmetry, where Co and Nb randomly sitting at B-site with lattice constant ~ 4.0496(2) Å. Rietveld refinement yields larger value of thermal parameters, implying Pb and O are disordered along <111> and <110> directions, respectively. The temperature dependent dielectric properties revealed re-entrant relaxor behaviour (Tm ~ 130 K and 210 K for 1 kHz) along with a high temperature diffused phase transition, Tc ~270 K. The low temperature frequency dependent dielectric maximum, f(Tm) is analyzed using generalized glass model (also called critical slowing down model). The magnetodielectric effect (MDE(%) = (ε’(9T)-ε’(0T))/ε’(0T)*100) depicts positive and negative MDEs implying coupling between mangnetic and dielectric properties. Such positive and negative MDEs are also observed in disordred double perovskite Pr2CoMnO6 whereas single MDE peak is reported in B-site ordered phase. Therefore, it is believed that the re-entrant relaxor behaviour and multiple positive-negative megnetodielectric effects are associated with the quenched disorder as well as multiple heterogeneities present in PCN ceramics and details will be discussed.