His feet were sore but his hopes were soaring after a message from his attorney, Eamon Dornan.
The Belfast man's stay in America had just been extended for another year.
"I was wondering if they would let me march in the parade and then tap me on the shoulder," McAllister told the Echo.
The tap never came. Instead it was a text that brought renewed hope for a permanent life in America for McAllister and two of his children, Nicola and Sean Ryan.
"I was very privileged to have marched with Ray Kelly, said McAllister who said that he hoped the coming year would bring news of permanent legal status.
"The bottom line is another year. It's a big relief, but you can never really settle," he said.
McAllister and his family fled Belfast in 1988 after loyalist gunmen fired into the family home. They first sought refuge in Canada before coming to the U.S. in the mid-1990s and settling in New Jersey. The family experienced tragedy in 2004 when Malachy's wife, Bernadette, died of cancer.