Познакомившись с Брукнером, Малер стал почитать его так же, как Вагнера. Брукнер увлеченно рассказывал о своем паломничестве в 1876 году на открытие театра в Байройте, ознаменовавшееся первым исполнением вагнеровской тетралогии «Кольцо нибелунга». Его живое участие в судьбах молодых талантов с постоянной готовностью бескорыстно их поддерживать, что-то советовать всегда вдохновляло юных музыкантов. В это время он активно работал над новой редакцией своей Третьей симфонии, премьера которой состоялась в декабре того же 1877 года. Однако оркестранты Венской филармонии саботировали это сочинение: по окончании симфонии они немедленно покинули сцену, не дождавшись аплодисментов, и композитор, в одиночестве стоя на опустевшем помосте, кланялся группе энтузиастов, среди которых был и Густав Малер. Восхищенный творением Брукнера, он самостоятельно осуществил переложение этой симфонии для фортепиано, которое вскоре вышло в свет благодаря издателю Раттигу.
Брукнер и Малер нашли друг друга: оба знали, что такое критика и непризнанность, испытывали любовь к Вагнеру и понимали стратегию развития искусства. Позднее дружба их так сплотила, что Брукнера стали называть приемным отцом Малера. Густав со своими друзьями нередко оказывался свидетелем столкновений Брукнера, в частности с критиком Гансликом, который постоянно разжигал страсти, обрушиваясь с беспощадной тирадой на Вагнера, а впоследствии и на Малера. Известно, что Ганслик пытался не допустить Брукнера к преподаванию в университете, но Брукнер всё же читал там гармонию и контрапункт, сделав теорию музыки частью университетской учебной программы.
Дружбу между Малером и Брукнером можно назвать духовным венцом консерваторских дней Густава. Сохранилось много историй, свидетельствующих о их привязанности и взаимном уважении. С другой стороны, чувство молодого Малера к Брукнеру было преклонением перед великим человеком. Он присутствовал на лекциях Брукнера в университете и видел, какой восторг они вызывали у слушателей. Юный и зрелый композиторы были настолько дружны, что вместе входили и выходили из здания университета. Малер являлся одним из немногих привилегированных гостей в доме Брукнера. Старший друг играл ему отрывки из сочиняемой в тот момент симфонии. Как высший знак уважения маэстро всегда провожал Густава, проходя все четыре лестничных пролета, и расставался с ним у двери на улицу. Вопрос, был ли Малер брукнеровским учеником, не столь важен ввиду неопровержимых доказательств существования их более глубокого взаимного чувства. Однако после смерти Малера было обнаружено письмо, отвечающее на этот вопрос: «Я никогда не был учеником Брукнера. Все думают, что я учился у него, потому что в студенческие годы в Вене часто был в его компании и числился среди его первых учеников. На самом деле, я думаю, что в свое время мой друг Кржижановский и я были его единственными последователями. Несмотря на большую разницу в возрасте между нами, веселый нрав Брукнера и его детская доверчивость сделали наши отношения чистой открытой дружбой. Естественно, понимание и реализация моих художественных и человеческих взглядов невозможны без его влияния. Поэтому я считаю, что, возможно, более оправданно, чем большинство других, называю себя его учеником, и всегда буду делать это с глубокой благодарностью».
Достоинство, непреклонность и прежде всего непоколебимая вера в истинность сказанного, которыми Брукнер отвечал на жестокие обвинения, возносили его выше всяческих нападок. Для Малера в этом заключался нравственный урок, который, несомненно, помогал не падать духом в течение многих лет, когда ему — неизвестному композитору отказывали в признании. Как и Брукнер, не уступавший любым попыткам недоброжелателей принизить или изменить его взгляды, Малер впоследствии никогда не шел на творческие компромиссы. Позже, став концертирующим дирижером, Густав всегда навещал Брукнера в Вене. Надпись, сделанная Малером при дирижировании «Те Deum» Брукнера, стала знаменитой. На обложке партитуры вместо привычных слов «Для солистов, хора и оркестра» он написал: «Для ангельских голосов, чистых сердец и душ, очищенных огнем».
Оценивая дарование Малера весьма высоко, Брукнер после занятий часто приглашал его выпить по кружке пива, за которой они обсуждали волнующие музыкальные проблемы. Так студенты Малер, Вольф и Ротт получали ответы на интересующие их вопросы: куда должна развиваться музыка, какова логика строения музыкального произведения, каковы задачи композиторского творчества. Эти ответы звучали не в консерватории.