Executing long-horizon procedures from natural language is challenging for LLM agents due to the lack of structure in free-form instructions like recipes or business workflows, often leading to execution drift or failure. We propose Procedure Aware DynaMic Execution (PADME), a framework that autonomously transforms procedural text into executable graphs capturing dependencies and decision logic. PADME employs a two-phase approach: a Teach phase for systematic structuring and an Execute phase for dynamic, real-time inputs and environment feedback-driven traversal. This graph-based representation provides an inductive bias that reduces error accumulation and ensures scalability. Empirically, PADME achieves state-of-the-art performance on four benchmarks, including ALFWorld and ScienceWorld, demonstrating that agents equipped with graph-based procedure representations offer a powerful intermediate abstraction for robust and generalizable execution.