On LinkedIn I stumbled over this interesting question (posed by Tony Bruce). Well, I clearly and loudly have to disagree.
Having guided several organizations from waterfall to agile, but also from chaos to agile I would definitively say that it is easier to transform a company without rigid methodology to agile, than to convert a waterfall styled company to agile.
There is a simple enough reason for this: it is much harder to break waterfall style habits (such as the big upfront design) in projects than it is to learn new agile habits from scratch. I find that even with organizations that came from waterfall and migrated successfully (!) to an agile approach, there is always a risk of projects going back to waterfall, even it the organization has never been able to realize waterfall projects with and change of success. People tend to be conservative. Not having to get rid of bad habits simply saves precious time and effort.
Moreover, most firm were never successful at waterfall. It I would agree to the question posed, that would automatically imply that such firms will also never be successful at agile. This is both awkward and not very logical.