The heat flow and physical properties package (HP$^3$) of the InSight Mars mission is an instrument package designed to determine the martian planetary heat flow. To this end, the package was designed to emplace sensors into the martian subsurface and measure the thermal conductivity as well as the geothermal gradient in the 0-5 m depth range. After emplacing the probe to a tip depth of 0.37 m, a first reliable measurement of the average soil thermal conductivity in the 0.03 to 0.37 m depth range was performed. Using the HP$^3$ mole as a modified line heat source, we determined a soil thermal conductivity of 0.039 $\pm$ 0.002 W m$^{-1}$ K$^{-1}$, consistent with the results of orbital and in-situ thermal inertia measurements. This low thermal conductivity implies that 85 to 95\% of all particles are smaller than 104-173 $\mu$m and suggests that any cement contributing to soil cohesion cannot significantly increase grain-to-grain contact areas by forming cementing necks, but could be distributed in the form of grain coatings instead. Soil densities compatible with the measurements are 1211$_{-113}^{+149}$ kg m$^{-3}$, indicating soil porosities of 61 \%.