Павел Иванович Мельников родился 22 октября 1819 г. в Нижнем Новгороде.

Род Мельниковых возник при царе Михаиле Феодоровиче, в конце XVII столетия. Шестеро Мельниковых было в числе "ближних людей", владевших в конце XVII века населенными имениями. Отец П. И.-ча, капитан Иван Иванович, 11-ти лет от роду был унтер-офицером лейб-гвардии Семеновского полка, а в 1801 году, будучи 12 лет, уволен к статским делам с чином коллежского регистратора. В 1807 г. он вступил, по выбору Казанского дворянства, в земское войско (милицию) и, по роспуске его, остался в военной службе, был в походах во время борьбы с Наполеоном, в 1819 году вышел в отставку из военной службы и до смерти своей (1837) служил по выборам дворянства Нижегородской губернии. Мать, Анна Павловна, урожд. Сергеева (дочь Нижегородского помещика), умерла в 1835 году.