Sim, ao contrário do WhatApp você pode adicionar o contato no Telegram sem a necessidade de fazer isso primeiro no aparelho telefônico. Para saber mais, clique aqui.