Ukończył filologię polską i religioznawstwo na Uniwersytecie Jagiellońskim w Krakowie. Pracował jako nauczyciel, niezależny dziennikarz, menedżer kultury i dyplomata ( w latach 1991–1996 i 2000–2004 był wicedyrektorem Instytutu Polskiego w Pradze, w latach 2006–2010 dyrektorem Instytutu Polskiego w Bratysławie, a następnie wicedyrektorem Międzynarodowego Funduszu Wyszehradzkiego w Bratysławie).
Jako poeta debiutował w 1980 roku na łamach „Tygodnika Powszechnego”. Opublikował kilkanaście zbiorów wierszy. Wiersze, prozę, przekłady i recenzje drukował między innymi w „bruLionie”, „Krasnogrudzie”, „Literaturze na Świecie”, „Europie”; współpracował z czasopismem dla dzieci „Czarodziejska Kura”.
Jedyny spośród „trzech najważniejszych debiutantów lat 80.” (według Mariana Stali; potwierdza to Nagroda „Arki” z 1988 roku za najbardziej znaczące wejście w literaturę ostatnich lat), który wciąż utrzymuje swoją wysoką rangę. Debiutował jako poeta w pełni ukształtowany, któremu silne wpływy surrealizmu (nie francuskiego wszakże, lecz czeskiego) nie mąciły ostrości widzenia świata, nie pozbawiały go też precyzji w intelektualnym i poetyckim „przetwarzaniu” zastanej rzeczywistości. Machej potrafi znakomicie wykorzystywać związki między dowcipem i metaforą, dzięki czemu nawet jego najpoważniejsze wiersze nie są patetyczne, a te najbardziej humorystyczne nie stanowią jedynie czczej rozrywki. Z wyrafinowaną swobodą posługuje się różnorodnymi wzorcami wiersza metrycznego (a także – co ciekawe – formą małego liryku prozą).
Jest też poetą żywo reagującym na aktualne wydarzenia i zjawiska życia publicznego – inspiracją może być dlań wywiad z Madonną, zabójstwo Versacego czy film o Basquiacie. Ważne miejsce w jego twórczości zajmuje erotyka, podana z barokową wystawnością, w pełni swoich metafizycznych odcieni, a jednocześnie nader sugestywna i niekiedy zdumiewająco śmiała. Wart zauważenia jest też poemat Zapiski spod wieży Babel (cały zbudowany z „wynalazków językowych” synka poety, Klaudiusza), a także trzy duże utwory: Prolegomena do dziejów poezji polskiej w latach dziewięćdziesiątych XX wieku (w poemacie dochodzi do rewindykacji wielu ustalonych mniemań dotyczących historii literatury najnowszej), Cztery litanie społeczno-ekonomiczne z lipca 2002 roku (rzadki dziś przykład wiersza politycznie zaangażowanego) i Kwestionariusz Karpowiczowski (hołd złożony jednemu z największych poetów polskich, stawiający jednocześnie pytanie o obowiązujące w polskiej krytyce systemy wartości). Twórczość Macheja jest tak rozmaita, że trudno ją zamknąć w zdaniach o charakterze ogólnym. Poeta ten nie tworzy wierszy „typowych”, w każdym tekście stara się zaskoczyć czytelnika i z reguły mu się to udaje.
W 2024 roku ukazał się pierwszy zbiór esejów Macheja Widokówki z niebytu. To osobiste świadectwo czytania polskiej literatury w czasach jej schyłku i degradacji jej znaczenia. Autor pisze o dziełach ważnych, a zapomnianych, przypomina postacie nieobecne we współczesnym dyskursie wokół literatury. Eseje miewają charakter wspomnieniowy, Machej odwołuje się bowiem również do własnych przeżyć czy znajomości, na przykład z Wisławą Szymborską i Tadeuszem Różewiczem.
Wiersze Macheja były tłumaczone na angielski, bułgarski, francuski, niemiecki, serbski i słowacki oraz były publikowane w licznych antologiach nowej polskiej poezji za granicą.
Autor jest laureatem nagrody krakowskiego kwartalnika „Arka” (1988), Nagrody Artystycznej Młodych im. Stanisława Wyspiańskiego (1991), Nagrody „Literatury na Świecie” (2017) i Nagrody Poetyckiej im. Konstantego Ildefonsa Gałczyńskiego „Orfeusz” (2021). Był również nominowany do Paszportów „Polityki” (2004, za Prolegomena), do Wrocławskiej Nagrody Poetyckiej Silesius (2008) oraz Nagrody Literackiej Gdynia (2008, za Wiersze przeciwko opodatkowaniu poezji).