Сын Публия Корнелия Лентула Марцеллина, происходившего из рода Клавдиев Марцеллов, но затем усыновлённого некой семьёй из рода Корнелиев Лентулов. В 70-х годах был квестором при Квинте Цецилии Метелле Пие в Испании. В 67 до н. э. был легатом Гнея Помпея во время его зачистки Средиземного моря от пиратов. Помпею он, видимо, был обязан своей карьерой, что Помпей припомнил Марцеллину впоследствии, когда он отвернулся от своего бывшего покровителя. Предположительно в 60 до н. э. Гней был претором, после чего был наместником в Сирии. В 56 до н. э. был консулом, был противником ещё существовавшего тогда первого триумвирата. В частности, Марцеллин публично задал Помпею и Крассу неприятный для них вопрос о том, собираются ли они выдвигать свои кандидатуры в консулы на 55 год до н. э.. Помпей ответил, «что, может быть, он будет домогаться консульства, а может быть, и нет», а Красс сказал, «что поступит так, как считает полезным для общего блага». После этого Марцеллин произнёс речь, направленную против Помпея, а Помпей ответил, что он сделал Марцеллина «из немого красноречивым, а из голодного пресыщенным обжорой».