The electromagnetic characteristics, particularly the real ε_r′ and imaginary ε_r″ parts of the dielectric constant, of new AlN-based composites with additions of powdered diamond, soot, and diamond with 3–5 wt.% molybdenum, synthesized by hot pressing, were studied at frequencies ranging from 12.4 to 18 GHz. Structural features and key phases of the composites—AlN, C (graphite), Al₃(O, N)₄, Al, and Mo₂C (in the AlN–Y₂O₃–C (diamond)–Mo system)—were determined by X-ray diffraction. Scanning electron microscopy with energy-dispersive X-ray analysis for determining the quantitative elemental composition of the key phases revealed a low oxygen content in the AlN lattice. Measurements of the electromagnetic characteristics showed that the new composites with graphite phase inclusions had stable dielectric characteristics over the entire frequency range (ε_r′ = 12.38–33.03 and tgδ = 0.009–0.214). The introduction of 3% diamond powder to the AlN-based charge hardly increased the ε_r′ and tgδ values (12.3 and 0.009, respectively). When a 5% : 5% mixture of diamond and molybdenum powders was added, the dielectric constant ε_r′ reached 17.04 and tgδ was 0.067. Composites with 5% soot demonstrated the highest dielectric constant (33.03) and dielectric losses (0.214). Thus, the dielectric constant was found to be increased through specific phase composition of the materials and dispersed distribution of conductive phases (C, Mo₂C) within the composites with minimal contacts between them.