Apesar de Khrushchev ainda não ter denunciado aquilo que o dissidente português então já pensava sobre o estalinismo, sendo expulso do PCP sob a acusação de titismo (o cisma jugoslavo é de 1948), Mário Soares referirá sempre os anos cinquenta como a sua "longa travessia do deserto". "Não é de estranhar", escreverá Fernando Rosas, que "cedo se tenha incompatibilizado com o que [ele e vários dos seus companheiros] entenderam ser os aspetos autoritários, despóticos e antidemocráticos do estalinismo e do próprio leninismo", advogando, antes, "um marxismo devolvido à sua "pureza", isto é, como então entendiam, "expurgado" das suas componentes autoritárias, burocráticas e repressivas" (O Presidente de Todos os Portugueses)..Enquanto muitos amigos da juventude, sobretudo após a notícia do Avante! ("A luta contra os oportunistas [um deles, era Soares] é a base do fortalecimento da luta pela democracia e pela paz"), lhe fizeram "um bloqueio afetivo, tentando [isolá-lo]", o que foi "um golpe duro" (Um Político Assume-se), outros antigos camaradas também andavam por essa época a ler, em francês, O Zero e o Infinito, de Arthur Koestler, Eu Escolhi a Liberdade, do dissidente soviético Victor Kravtchenko, De Volta da URSS, de André Gide, a nova revista France Observateur, ainda títulos do ex-comunista jugoslavo Milovan Djilas ou do marxista heterodoxo francês Henri Lefèbvre, os três volumes da biografia de Trotski, A Engrenagem, de Jean-Paul Sartre, ou Autocrítica, de Edgar Morin..E se Mário Soares, como admitiu posteriormente, "não tinha, politicamente, para onde ir" (Ditadura e Revolução), os outros estavam com o mesmo dilema. Após esse período de profunda reflexão individual - pois se esses anos "foram bastante calmos no plano da intervenção política, [seriam] fecundos do ponto de vista da reflexão e da aprendizagem teórica" (Uma Vida) - , poderia repetir, no resto da sua vida, o que respondeu à bancada parlamentar do PCP, em 1983, durante a apresentação do programa do Governo do Bloco Central: "Estou no lugar onde sempre estive, mesmo quando julgava que era comunista" - o socialismo. Foi então que "[compreendeu] - e não [se enganou] - que para derrubar o salazarismo, num mundo dividido em dois blocos rivais, era necessário que a Oposição Democrática, desde o final da [II] Guerra [Mundial]fortemente influenciada pelo PCP, se libertasse dessa tutela incómoda. Daí a "longa marcha" que [empreendeu] até à refundação do Partido Socialista, membro de pleno direito da Internacional Socialista. Foi um caminho que passou pelo neutralismo, que [o] aproximou do terceiro-mundismo (Nehru, Tito, Nasser, Sukarno) e dos movimentos anticolonialistas, que desembocou numa total autonomia estratégica em relação ao PCP" (A Crise? E Agora?). No fundo, já revelava a qualidade com que a poetisa Natália Correia o definiu, na época da Presidência: "imbatível de intuição", revelaria Fernando Dacosta em O Botequim da Liberdade..Um conjunto de pessoas, onde se juntavam os expulsos do PCP e elementos da já extinta União Socialista, de António Macedo e José Magalhães Godinho a Salgado Zenha e Catanho de Menezes, em 1953 formam um grupo de reflexão, pressão e ação política chamado Resistência Republicana e Socialista , acabando depois por aderir, em 1956, ao Diretório Democrático--Social (dirigido por António Sérgio, Jaime Cortesão e Azevedo Gomes). Mas, no fundo, só voltará a ter atividade relevante na campanha de Humberto Delgado (outra página). Finalmente, em 1961, seria redator e signatário do "Programa para a Democratização da República", que, nas palavras de Raul Rego, "levou à cadeia meia centena de signatários e à polícia todos eles" (Diário Político [1968])..O ano crucial é 1964, quando Mário Soares (o único que continuava no país), Tito de Morais (então exilado em Argel, mas que se mudaria depois para Roma) e Ramos da Costa (já forçado a viver em Paris) decidem, em Genebra, fundar a Ação Socialista Portuguesa (ASP), organização parapartidária que será o embrião do PS. Já antes, lembrará Tito de Morais, em O "Portugal Socialista" na Clandestinidade, "em 1962, Mário Soares, Piteira Santos e eu reunimo-nos num café em Paris para darmos os últimos retoques à Declaração de Princípios desse movimento socialista que deveria de servir de base ideológica ao grande movimento socialista que todos tínhamos em mente construir. Piteira Santos afastou-se de nós, mas a ideia continuou fazendo a sua estrada"..Dois anos depois, em abril, no Hotel Moderne da cidade helvética, assinaram a primeira Declaração de Princípios da ASP e elegeram como secretário-geral Mário Soares - que ali estava "em representação do numeroso grupo de socialistas que, em Portugal, acedera a participar numa organização clandestina de luta contra o fascismo e pela construção de uma sociedade socialista" (ibidem). Decidiram ainda ter um jornal, impresso no estrangeiro, embora destinado ao interior, mas, como lembrava Tito de Morais, "só três anos depois foi possível tornar o Portugal Socialista uma realidade" (idem).."Combinando a herança nacional da oposição demoliberal com os postulados ideológicos do socialismo", regista o historiador Hipólito de la Torre Gómez, Soares "fundou a Ação Socialista Portuguesa (ASP), iniciativa afortunada que viria a entrar em sintonia com as aspirações das novas classes médias e profissionais, não comunistas, mas abertamente orientadas para fórmulas de progressismo democrático" (O Estado Novo de Salazar). No entender de Juliet Antunes Sablosky, ainda "não era um partido político enquanto tal, mas antes um conjunto de personalidades com opiniões convergentes sobre alguns aspetos da teoria socialista", cuja Declaração de Princípios, difundida em 1970, "radicava diretamente em [José] Fontana, [Antero de] Quental e [António] Sérgio, constituindo uma amálgama de socialismo utópico português e republicanismo" (O PS e a Transição para a Democracia)..Simultaneamente, há outras facetas que o vão tornando uma figura singular. "Como nenhum opositor da época", escreveu José Freire Antunes, "Soares compreendeu o poder da Imprensa ocidental na criação - inevitavelmente aleatória - de factos políticos sobre um país periférico e sem liberdades formais" (Nixon e Caetano), tornando-se rapidamente amigo de, entre outros, a jornalista Marvine Howe, que veio, em 1963, para a delegação do New York Times em Lisboa. E também das embaixadas dos países livres, a ponto de, lembrou Teresa de Sousa, a PIDE chegar "a filmar almoços que Soares oferece a representantes diplomáticos na sua casa em Nafarros" (Os Grandes Líderes)..Nas eleições de 1965, como regista Franco Nogueira na biografia de Salazar, o líder da ASP, um dos "nomes já veteranos" contra o regime, é candidato a deputado pela Oposição Democrática. Mas será na sua faceta de socialista que irá ganhar uma dimensão internacional. Nesse mesmo ano, escreve uma carta a solicitar a admissão da ASP na Internacional Socialista, que só se concretizará em 1972, no XII Congresso da IS, em Viena. Entretanto, os dirigentes da ASP escrevem aos socialistas franceses, aos sociais-democratas alemães e suecos, aos trabalhistas ingleses para estabelecer relações, participar nas conferências dos líderes dos partidos socialistas europeus, pedir apoios - e foi no congresso da IS em Eastbourne, corria o ano de 1969, no qual discursou, que Mário Soares conheceu o seu futuro grande amigo, o alemão Willy Brandt.