Вальдю родился в селе Монгол (ныне Ульчский район Хабаровского края).
В 1927 году стал учиться в школе-интернате в селе Ухта. Позже поступил в Дальневосточный педагогический техникум народов Севера в Хабаровске.Работал учителем начальной школы, секретарём исполкома районного Совета депутатов трудящихся. После окончания двухгодичных курсов партийных работников (1948) занимался партийной работой, был редактором районной газеты «Красный Север» в селе Богородском и местного радиовещания. Член Союза писателей СССР с 1972 года.Первые рассказы, очерки, зарисовки Вальдю были опубликованы в местной печати в 1940-е годы. Отдельным изданием его первая книга «Жизнь и сказка» вышла в Хабаровском книжном издательстве в 1956 году.
В 1960-70-е годы на ульчском языке были опубликованы переработанные им ульчские и нанайские народные сказки. Так, в Ленинграде на ульчском языке выходят «Сказки народа нани» (1961), позже в Хабаровске «Сказки бабушки Лайчи» (1972).Крупный сборник произведений Вальдю был издан в Москве издательством «Современник» в 1974 году.
В него вошли повести «Сойнган — сын своего народа» и «Месяц первых цветов» , а также другие произведения.
В 1984 году вышла его повесть «Свет в окне» . Очерк воспоминаний «Откуда наступает рассвет» стал последним произведением писателя.Алексей Вальдю говорил: Давно мечтал я поведать людям легенды и сказки моего народа.Алексей Леонтьевич Вальдю Заслуженный работник культуры РСФСР, награждён орденом Знак Почета.Э. Л. Богатырева, его дочь, закончившая художественно-графический факультет Хабаровского пединститута, передала в архив Хабаровского края интереснейшие материалы о жизни и творчестве Алексея Леонтьевича, в том числе рукописи произведений, переписку с писательницей Ю. А. Шестаковой, документы личного характера.