We study unconventional superconductivity in thin exfoliated single crystals of a promising 3D topological superconductor candidate, Nb-doped Bi$_2$Se$_3$ through Andreev reflection spectroscopy and magneto-transport. Measurements of Andreev reflection in low and high resistance samples both show enhanced conductance around zero bias and conductance dips at the superconducting energy gap. Such behavior is inconsistent with conventional Blonder-Tinkham-Klapwijk theory of Andreev reflection. We discuss how our results are consistent with $p$-wave pairing symmetry, supporting the possibility of topological superconductivity in Nb-doped Bi$_2$Se$_3$.