The foundation of Agile software development is Test Driven Development, Continuous Integration and Continuous Deployment. Without these 3 things in place you're not being or doing Agile you're building a Fragile system that will eventually fall apart. There are of course exceptions to every rule and there are edge cases that are working quite well for some people but I'm talking about the general case.
There's already a lot written about Test Driven Development and how to do it properly so if this is a new subject for you I'll just give a high level introduction. As the name suggests you start with Test's, these usually come in the form of either Unit Tests or Acceptance Tests. The ideal you should strive for is a high level of coverage for both types of test and it's generally OK if you never reach that 100% coverage mark.
Unit Tests will focus on one piece of the code to make sure that it does what you expect, you write the failing test, run it to see it fail, write the code that will pass it and run it again to see it pass. It takes time to get used to developing software this way but the process encourages you to break the problems down into small enough pieces that you end up writing the code in less time overall than if you tried to do it all at once. There are many other benefits like never ending up with code you don't need/use etc. but that's too detailed to go into here.
Acceptance Tests take a bit more work to set up but the time spent is well worth it. These are end to end tests of the software/system as a whole that verify the functionality works as expected. Again these should be set up as much as possible before writing the actual code but sometimes you'll need to build some basic pieces in order to be able to run the test. An acceptance test may stay in the failing state while the functionality is being built but once they pass (usually you'll have many tests for one feature) you can be sure that the feature is finished. Part of the Acceptance test process should always be to build the set up and automated deployment of the software, this helps to identify potential road blocks you would normally run into once you're "finished" where most software hits the well known "the last 10% takes 90% of the time" problem.
At this point you have automated Unit Tests for the internal logic, automated Acceptance Tests for the features and automated deployment and integration all set up. This is the foundation you're going to use in order to develop quickly while still maintaining the existing code and features. With each new feature added if you keep this process up you have a full regression suite that runs automatically to ensure the software is stable and the current functionality is always kept intact. You may be thinking "of course this is obvious", well you're probably a software developer who already knows all of this or a technically minded person.
Why is the foundation, the most important and arguably the only necessary part the one that somehow escapes the initial migration to Agile software development? The main reason is it's initially hard, it takes a lot of time and effort to put in place, specially with existing legacy software and it will slow things down while it's being set up. If you're hiring a consultant to come in and make the department or organization Agile and they have 2 weeks or a month to do this then they can't produce a measurable improvement in that amount of time (unless you have no existing software to start with). So they take the process's and practices that will give them a quick win to get their large consulting fee and move on to the next company while ignoring all of the hard but necessary things that should be in place first.
Since the majority of people will need to deal with legacy systems while getting this set up I'm going to tell you that your software is probably not in the best condition to go in and start writing unit tests. If you try you're probably going to have to rewrite it and in the process you're going to break things and that's going to be very demotivating. The best approach for legacy systems is to put the Acceptance Tests in place first and try to cover as much of the functionality as you can. This will give enough confidence to be able to get in and start rewriting the code and add unit tests because the Acceptance Tests will let you know when you've broken something. Another good practice to have that will help with legacy code as well as maintaining your new code is to write a test to reproduce a bug when one is found. This can be either a unit test or acceptance test or both in some cases but the first step should always be to reproduce the bug with a test that can be automated. Once you have the test in place go ahead and fix the bug and run the test to verify it, now you can be sure that bug will never rear it's ugly head again.
OK my company now has all of this in place and we're releasing stable software every week, this is awesome! I can fire my whole QA department and save the company even more money right?
Well maybe but probably not, QA will almost always be necessary because most software is being written to be used by humans and there's never a replacement for a real live human actually using the software to make sure it's working properly. Your QA department should actually be the ones helping to set up the Acceptance Tests to ensure the feature has enough automated coverage as well as doing exploratory testing with the software to make sure the UI doesn't have any bugs since UI testing is extremely hard to automate and is generally not worth the time and effort.
If you're in the process of having Agile introduced to your company and you don't see the foundation even being mentioned now would be a great time to bring this up and get your technical people involved. If you've tried Agile and had it fail I'd like to know if any of this information is new to you, I'm always interested in knowing when it just doesn't work even when it's done properly. If you're looking at moving to a company claiming to be Agile just ask what percentage of Acceptance Test coverage and Unit Test coverage they generally aim for and how long it took them to get there. If you get an open mouthed blank stare or the equivalent of a politician's response back then it's time to thank them for their time and move on.